The present invention relates to cryptographic systems, and, more particularly, is directed to elliptic curve cryptosystems in which participants pick their own elliptic curves rather than using a centrally chosen elliptic curve.
In a conventional elliptic curve cryptosystem, as shown in FIG. 1, a central facility selects a finite field, an elliptic curve, a generator of an appropriate subgroup of the group of points of the elliptic curve over the finite field, and the order of that generator. The central facility distributes these data among the participants in the cryptographic system. Each participant then selects a secret key, computes a corresponding public key, and may optionally obtain certification for its public key. The objective of the certificate is to make one party""s public key available to other parties in such a way that those other parties can independently verify that the public key is valid and authentic. An advantage of the conventional system is that, while a lot of computation is required to obtain both the cardinality of the group of points of an elliptic curve over a finite field, and to find an elliptic curve for which this cardinality satisfies the security requirements, this computation need not be performed by participantsxe2x80x94which would be very burdensomexe2x80x94as the computation is performed once by the central facility.
Conventional elliptic curve cryptosystems are used in the same applications as public key cryptosystems, such as authentication, certification, encryption/decryption, signature generation and verification.
As shown in FIG. 2, to use the conventional elliptic curve cryptosystem, two parties wishing to communicate exchange their cryptographic data, and then proceed with their communication, such as a signature scheme or a data encryption/decryption scheme. Advantageously, the number of bits exchanged during communication setup between parties is small.
A serious problem with the above-described conventional elliptic curve cryptosystem is that all participants are vulnerable to an attack on the centrally selected elliptic curve and finite field. That is, the system is vulnerable to a concentrated attack on the Discrete Logarithm problem in the group defined by the centrally selected elliptic curve and finite field.
Due to the desire that the cryptographic functionality be implementable in a small, inexpensive, low power device, it is considered impractical for each participant to choose its own elliptic curve. More particularly, allowing each participant to choose its own elliptic curve improves system security but results in a complicated system setup phase.
In conventional elliptic curve cryptosystems, the number of bits exchanged between parties during communication set-up is small, typically representing the parties"" identities and the parts of their public keys that differ, i.e., not the curve and field shared by all parties. If each participant chose its own elliptic curve, another disadvantage would be that more data would have to be exchanged during communication set-up, specifically, the complete public keys including curves and fields would have to be exchanged during communication setup.
In view of these issues, there is a need to reduce the vulnerability to attack of elliptic curve cryptosystems.
In accordance with an aspect of this invention, there is provided a method of establishing a cryptographic system among participants, comprising the steps of: selecting a curve E from a predetermined set of elliptic curves, selecting a finite field, selecting a secret key, and obtaining a public key, wherein the steps of selecting a curve E, a finite field, a secret key and obtaining a public key are performed locally by each of the participants.
In an embodiment of the present invention, the predetermined set of elliptic curves are expressed as Weierstraxcex2 model equations, specifically:
y2=x3+0x+16;
y2=x3xe2x88x92270xxe2x88x921512;
y2=x3xe2x88x9235xxe2x88x9298;
y2=x3xe2x88x929504xxe2x88x92365904;
y2=x3xe2x88x92608x+5776;
y2=x3xe2x88x9213760x+621264;
y2=x3xe2x88x92117920x+15585808;
and
y2=x3xe2x88x9234790720x+78984748304.
In an embodiment of the present invention, the step of obtaining a public key includes selecting a bitstring s having a predetermined length based on security considerations, and obtaining a prime number p based on the selected bitstring s and a unique bitstring ID of the respective participant.
In accordance with an aspect of this invention, there is provided a method of reconstructing a public key for a participant in a cryptographic system, comprising the steps of forming intermediate integers a and b based on the participant""s ID, obtaining a prime number p as a function of the intermediate integers a and b, selecting a curve E from a predetermined set of elliptic curves, picking a point Q on the selected curve based on the participant""s ID, and constructing the public key from the prime number p, the selected curve E and the point Q.
In an embodiment of the present invention, the predetermined set of elliptic curves are expressed as Weierstraxcex2 model equations.
It is not intended that the invention be summarized here in its entirety. Rather, further features, aspects and advantages of the invention are set forth in or are apparent from the following description and drawings.